package com.zp.self.module.level_4_算法练习.算法.动态规划;

/**
 * @author By ZengPeng
 */
public class 力扣_91_解码方法 {
    //测试
    public static void main(String[] args) {

        System.out.println(new 力扣_91_解码方法().numDecodings("12"));
        System.out.println(new 力扣_91_解码方法().numDecodings("226"));
        System.out.println(new 力扣_91_解码方法().numDecodings("0"));
        System.out.println(new 力扣_91_解码方法().numDecodings("121239213921923912"));
        System.out.println(new 力扣_91_解码方法().numDecodings("2101"));
        System.out.println(new 力扣_91_解码方法().numDecodings("10011"));
        System.out.println(new 力扣_91_解码方法().numDecodings("100"));
        System.out.println(new 力扣_91_解码方法().numDecodings("4673351343232714528787622144828949686814115978657763689251918941228645575658338815495647817194659305"));
    }

    /**
     题目：一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：
     'A' -> "1"
     'B' -> "2"
     ...
     'Z' -> "26"
     要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。
     例如，"11106" 可以映射为：
     "AAJF" ，将消息分组为 (1 1 10 6)
     "KJF" ，将消息分组为 (11 10 6)
     注意，消息不能分组为  (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。
     给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。
     题目数据保证答案肯定是一个 32 位 的整数。

     示例 1：
     输入：s = "12"
     输出：2
     解释：它可以解码为 "AB"（1 2）或者 "L"（12）。

     示例 2：
     输入：s = "226"
     输出：3
     解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

     示例 3：
     输入：s = "0"
     输出：0
     解释：没有字符映射到以 0 开头的数字。
     含有 0 的有效映射是 'J' -> "10" 和 'T'-> "20" 。
     由于没有字符，因此没有有效的方法对此进行解码，因为所有数字都需要映射。

     分析：【P 💔💘💞】
     1.递归+动态规划：两个值连起来<=26 记得分两种情况递归求和，注意不能以0开头
         当前值可以出现两种情况时：fun(n) = fun(n+1) +fun(n+2)
         当前值不可以出现两种情况时：fun(n) = fun(n+1)
     优化：arr 带备忘录的递归 【否则存在多次重复运算而超时】
        --执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

     边界值 & 注意点：
     1."2101"  0的处理，只能黏住前面一位
     2."10011"  错误0的处理,判断出异常情况
     **/
    public int numDecodings(String s) {
        char[] chars = s.toCharArray();
        if (chars[0] == '0') return 0;
        int[] arr = new int[chars.length];
        for (int i = 0; i < arr.length; i++)
            arr[i]=-1;
        return dsf(chars, 0, arr);
    }

    private int dsf(char[] chars, int start, int[] arr) {
        if (start >= chars.length) return 1;
        if (arr[start] != -1 ) return arr[start];
        int current = chars[start] - '0';
        if (current == 0) {
            if (chars[start - 1] - '0'==0 ||chars[start - 1] - '0' > 2)// 错误0的处理,判断出异常情况 ,这里当前位只能一个0时，返回0。正常情况则直接求下一个递归值
            arr[start] = 0;
        } else if (current == 1) {
            if (start < chars.length - 1) {//此时长度够，还有下一位，判断能否分为两种情况
                int next = chars[start + 1] - '0';
                if (next != 0) {
                    if (!(start < chars.length - 2 && chars[start + 2] == '0'))
                        arr[start] = dsf(chars, start + 1, arr) + dsf(chars, start + 2, arr);
                }
            }
        } else if (current == 2) {
            if (start < chars.length - 1) {//此时长度够，还有下一位，判断能否分为两种情况
                int next = chars[start + 1] - '0';
                if (next != 0 && next < 7) {
                    if (!(start < chars.length - 2 && chars[start + 2] == '0'))
                        arr[start] = dsf(chars, start + 1, arr) + dsf(chars, start + 2, arr);
                }
            }
        }
        if (arr[start] == -1) arr[start] = dsf(chars, start + 1, arr);
        return arr[start];
    }
}
